//
// Created by lwj12 on 24-8-25.
//

#ifndef BINARYSEARCHTREE_BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_BINARYSEARCHTREE_H
using namespace std;

namespace lwj
{
    template<class K>
    struct BSTNode
    {
        K _val;
        BSTNode* _left;
        BSTNode* _right;

        BSTNode(const K& val)
            : _val(val),
              _left(nullptr),
              _right(nullptr)
        {}
    };

    template<class K>
    class BST
    {
    public:
        typedef BSTNode<K> Node;

        BST() = default;
        BST(const BST& bst){_root = Copy(bst._root);}

        ~BST() {Destroy(_root); _root = nullptr;}

        bool insert(const K& val)
        {
            if(_root == nullptr)
            {
                _root = new Node(val);
                return true;
            }
            Node* root = _root, *father = nullptr;
            while (root)
            {
                if(root->_val < val)
                {
                    father = root;
                    root = root->_right;
                }
                else if(root->_val > val)
                {
                    father = root;
                    root = root->_left;
                }
                else return false;
            }
            if(val > father->_val) father->_right = new Node(val);
            else father->_left = new Node(val);
            return true;
        }

        bool erase(const K& val)
        {
            Node* root = _root, *father = nullptr;
            while (root)
            {
                if(root->_val < val)
                {
                    father = root;
                    root = root->_right;
                }
                else if(root->_val > val)
                {
                    father = root;
                    root = root->_left;
                }
                else
                {
                    if(root->_right && root->_left)
                    {
                        Node* tmp = father = root;
                        root = root->_right;
                        while (root->_left)
                        {
                            father = root;
                            root = root->_left;
                        }
                        tmp->_val = root->_val;
                    }
                    if(root->_left)
                    {
                        if(father == nullptr) _root = root->_left;
                        else if(father->_val > root->_val) father->_left = root->_left;
                        //else if(father->_left == root) father->_left = root->_left;
                        else father->_right = root->_left;
                    }
                    else
                    {
                        if(father == nullptr) _root = root->_right;
                        else if(father->_val > root->_val) father->_left = root->_right;
                        //else if(father->_left == root) father->_left = root->_right;
                        else father->_right = root->_right;
                    }
                    delete root;
                    root = nullptr;
                    return true;
                }
            }
            return false;
        }

        bool find(const K& val)
        {
            Node* root = _root;
            while (root)
            {
                if(root->_val < val) root = root->_right;
                else if(root->_val > val) root = root->_left;
                else return true;
            }
            return false;
        }

        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }

    private:
        void _InOrder(Node* root)
        {
            if(root == nullptr) return;
            _InOrder(root->_left);
            cout << root->_val << ' ';
            _InOrder(root->_right);
        }

        void Destroy(Node* root)
        {
            if(root == NULL) return;
            Destroy(root->_left);
            Destroy(root->_right);
            delete root;
        }

        Node* Copy(Node* root)
        {
            if(root == nullptr) return nullptr;
            Node* newRoot = new Node(root->_val);
            newRoot->_left = Copy(root->_left);
            newRoot->_right = Copy(root->_right);
            return newRoot;
        }

        Node* _root = nullptr;
    };
}

#endif//BINARYSEARCHTREE_BINARYSEARCHTREE_H
